package com.qjc.demo.algorithm.反转链表LeetCode206;

/**
 * @ClassName: Solution
 * @Author: qjc
 * @Date: 2023/8/16 09:50
 */
public class Solution {

    // 通过递归方式反转
    public static ListNode reverseDiGui(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode reverseNode = reverseDiGui(head.next);
        head.next.next = head;
        head.next = null;
        return reverseNode;
    }

    // 使用迭代的方式进行反转
    public static ListNode reverseList(ListNode head) {
        // 采用一个临时节点进行指针反转
        ListNode pre = null;
        ListNode temp = null;
        ListNode cur = head;
        while (cur != null) {
            // 先把当前节点的下一个节点赋给临时节点
            temp = cur.next;
            // 将当前节点指向前一个节点
            cur.next = pre;
            // 把前一个节点和当前节点都往后移一个节点
            // 前一个节点变成当前节点
            pre = cur;
            // 当前节点变成下一个节点
            cur = temp;
        }
        // 最后前一个节点就变成了最后一个节点
        return pre;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(3);
        ListNode head4 = new ListNode(4);
        head.next = head2;
        head2.next = head3;
        head3.next = head4;
        // 初始链表打印
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.getVal());
            temp = temp.next;
        }
        System.out.println();
        // 反转后链表打印
        ListNode listNode = reverseList(head);
        while (listNode != null) {
            System.out.print(listNode.getVal());
            listNode = listNode.next;
        }

    }

}
